(function (exports) {
    'use strict';

    /**
     * An object that will be used as the item in the sequences to sort.
     */
    function Item(x, rank) {
        /**
         * The key to use in sort.
         * @type {number}
         */
        this.x = x;
        /**
         * The rank of the item in the original sequence.
         * @type {number}
         */
        this.rank = rank;
    }

    Item.prototype.toString = function () {
        return this.x + '(' + this.rank + ')';
    };

    /**
     * Build an array of {@link Item} instances sorted according to
     * <tt>x</tt>.
     * @param {number} n the number of elements in the array
     * @return {Item[]}
     */
    function buildSortedArray(n) {
        var i, j, out;

        out = new Array(n);

        for (j = i = 0; i < n; ++i) {
            out[i] = new Item(j, i);
            if (Math.random() > 0.01) {
                ++j;
            }
        }

        return out;
    }

    function buildIdentityArray(n) {
        var out;

        out = new Array(n);
        while (n--) {
            out[n] = new Item(5, n);
        }

        return out;
    }

    /**
     * Randomize an array of {@link Item} instances.
     * @param {Item[]} the array to randomize
     * @return {Item[]} return the array
     */
    function randomizeArray(array) {
        var n, i, j, t, array;

        // do a random permutation
        n = array.length;
        for (i = 0; i < n - 1; ++i) {
            // exchange i-th object any object in range [i,n) (i-th
            // included)
            j = Math.floor(Math.random() * (n - i)) + i;

            t = array[i];
            array[i] = array[j];
            array[j] = t;
        }

        // renumber ranks
        for (i = 0; i < n; ++i) {
            array[i].rank = i;
        }

        return array;
    }

    var MAX_N = 500000;
    var REPEAT = 20;
    var SIZE_STEPS = [0, 1, 10, 100, 500, 1000, 10000, 100000, 500000];

    var ordered = buildSortedArray(MAX_N);
    var ordered_identical = buildIdentityArray(MAX_N);
    var unordered = randomizeArray(buildSortedArray(MAX_N));

    function compItems(item1, item2) {
        return item1.x - item2.x;
    }

    function median(seq) {
        var copy, l;
        copy = seq.slice();
        copy.sort(function (x, y) { return x - y; });
        l = copy.length;
        if (l === 0) {
            return NaN;
        } else if (l & 1) {
            return copy[l >> 1];
        } else {
            return (copy[l >> 1] + copy[(l >> 1) - 1]) / 2;
        }
    }

    function mean(seq) {
        var i, l, sum;
        sum = 0;
        for (i = 0, l = seq.length; i < l; ++i) {
            sum += seq[i];
        }
        return sum / l;
    }

    function testAlgos(tests, progresscb) {
        var t_i, t_l, test, d_i, d_l, inputs, input,
            r, s_i, s_l, s, seq, ref, start, dt, i, notStable, dts, limit,
            progress, progress_limit,
            stats_size, stats_sizes, stats_inputs;

        inputs = [{id:'ordered', data: ordered, refs: {}}, {id: 'unordered', data: unordered, refs: {}}, {id:'identical', data: ordered_identical, refs: {}}];
        stats_inputs = {};
        progress_limit = inputs.length * SIZE_STEPS.length * tests.length * REPEAT;
        progress = 0;
        for (d_i = 0, d_l = inputs.length; d_i < d_l; ++d_i) {
            input = inputs[d_i];
            stats_sizes = {};
            for (s_i = 0, s_l = SIZE_STEPS.length; s_i < s_l; ++s_i) {
                s = SIZE_STEPS[s_i];
                stats_size = {};
                for (t_i = 0, t_l = tests.length; t_i < t_l; ++t_i) {
                    test = tests[t_i];
                    limit = test.limits[input.id] || test.limits['*'] || Infinity;
                    if (s > limit) {
                        progress += REPEAT;
                        if (progresscb) { progresscb(progress, progress_limit); }
                        continue;
                    }
                    dts = [];
                    for (r = 0; r < REPEAT; ++r) {
                        seq = input.data.slice(0, s);
                        if (input.refs.hasOwnProperty(s)) {
                            ref = input.refs[s];
                        } else {
                            ref = input.data.slice(0, s);
                            ref.sort(compItems);
                            input.refs[s] = ref;
                        }
                        start = Date.now();
                        test.func(seq);
                        dt = Date.now() - start;
                        dts.push(dt);

                        // check validity
                        for (i = 0; i < s; ++i) {
                            if (seq[i].x !== ref[i].x) {
                                throw new Error('Sort function ' + test.name + ' failed to sort sequence:\n' + input.data.slice(0, s) + '\noutput is:\n' + seq + '\nbut should be:\n' + ref);
                                return
                            }
                        }

                        // output times
                        //console.log('- ' + test.name + '(' + input.id + '[' + s + ']) ' + dt + 'ms');
                        ++progress;
                        if (progresscb) { progresscb(progress, progress_limit); }
                    }
                    // output statistics
                    //console.log('= ' + test.name + '(' + input.id + '[' + s + ']) ' + median(dts) + 'ms');
                    //console.log();
                    stats_size[test.name] = { median: median(dts), mean: mean(dts), samples: dts }
                }
                stats_sizes[s] = stats_size;
            }
            stats_inputs[input.id] = stats_sizes;
        }
        return stats_inputs;
    }

    function arraySort(seq) {
        return seq.sort(compItems);
    }

    function insertionSort(seq) {
        var i, l, j, t;
        for (i = 0, l = seq.length; i < l; ++i) {
            t = seq[i];
            for (j = i; j --> 0 && seq[j].x > t.x; ) {
                seq[j + 1] = seq[j];
            }
            seq[j + 1] = t;
        }
    }

    function heapSort(seq) {
        var i, n, t;

        function siftDown(i) {
            var left, right, v, maxchild_i, maxchild_v, t;

            for (;;) {
                left = (i << 1) + 1;
                if (left >= n) {
                    break;
                }

                maxchild_i = left;
                maxchild_v = seq[left].x;
                
                right = left + 1;
                if (right < n && (v = seq[right].x) > maxchild_v) {
                    maxchild_v = v;
                    maxchild_i = right;
                }

                v = seq[i].x;
                if (v < maxchild_v) {
                    t = seq[maxchild_i];
                    seq[maxchild_i] = seq[i];
                    seq[i] = t;
                    i = maxchild_i;
                } else {
                    break;
                }
            }
        }


        n = seq.length;
        if (n <= 1) {
            return;
        }
        
        // transform seq into a heap
        for (i = n >> 1; i --> 0; ) {
            siftDown(i);
        }
        
        // put top heap element at end of array until no more elements
        // in heap
        for (; n --> 0;) {
            t = seq[n];
            seq[n] = seq[0];
            seq[0] = t;
            siftDown(0);
        }
    }

    function mergeSort(seq) {
        var target = new Array(seq.length);
        function rec(i, j) {
            var m, l, k, k1, k2;
            l = j - i;
            if (l <= 1) {
                return;
            }
            m = i + (l >> 1);
            rec(i, m);
            rec(m, j);

            for (k1 = i, k2 = m, k = i; k1 < m && k2 < j; ++k) {
                if (seq[k1].x < seq[k2].x) {
                    target[k] = seq[k1++];
                } else {
                    target[k] = seq[k2++];
                }
            }
            for (; k1 < m; ++k1, ++k) {
                target[k] = seq[k1];
            }
            for (; k2 < j; ++k2, ++k) {
                target[k] = seq[k2];
            }
            for (k = i; k < j; ++k) {
                seq[k] = target[k];
            }
        }
        rec(0, seq.length);
    }

    function quickSort(seq) {
        function rec(s, e) {
            var l, m, t, pivot, i, j;
            l = e - s;
            if (l <= 1) {
                return;
            }

            // choose a pivot
            m = s + (l >> 1);
            pivot = seq[m].x;

            // put the pivot at the end of array
            t = seq[e-1];
            seq[e-1] = seq[m];
            seq[m] = t;

            // put all elements smaller than pivot at the start
            for (i = j = s; j < e - 1; ++j) {
                if (seq[j].x <= pivot) {
                    t = seq[i];
                    seq[i] = seq[j];
                    seq[j] = t;
                    ++i;
                }
            }

            // put the pivot back in place
            t = seq[i];
            seq[i] = seq[e-1];
            seq[e-1] = t;

            // recurse on sub-arrays
            rec(s, i);
            rec(i + 1, e);
        }
        rec(0, seq.length);
    }

    function quickSort2(seq) {
        function rec(s, e) {
            var l, m, t, pivot, i, j, n, cr;
            for (;;) {
                l = e - s;
                if (l <= 1) {
                    return;
                }

                // choose a pivot
                m = s + (l >> 1);
                pivot = seq[m].x;

                i = j = s;
                n = e - 1;
                while (j <= n) {
                    cr = seq[j].x - pivot;
                    if (cr < 0) {
                        t = seq[i];
                        seq[i] = seq[j];
                        seq[j] = t;
                        i += 1;
                        j += 1;
                    } else if (cr > 0) {
                        t = seq[n];
                        seq[n] = seq[j];
                        seq[j] = t;
                        n -= 1;
                    } else {
                        j += 1;
                    }
                }

                // recurse on sub-arrays
                rec(s, i);
                // recursion on second sub-array is handled by loop
                // (tail call optimization)
                s = n + 1;
            }
        }
        rec(0, seq.length);
    }

    function funcQuickSort(seq, comp) {
        function rec(s, e) {
            //if (++limit > 50) { throw new Error(); }
            var l, m, t, pivot, i, j;
            l = e - s;
            if (l <= 1) {
                return;
            }

            // choose a pivot
            m = s + (l >> 1);
            pivot = seq[m];

            // put the pivot at the end of array
            t = seq[e-1];
            seq[e-1] = seq[m];
            seq[m] = t;

            // put all elements smaller than pivot at the start
            for (i = j = s; j < e - 1; ++j) {
                if (comp(seq[j], pivot) <= 0) {
                    t = seq[i];
                    seq[i] = seq[j];
                    seq[j] = t;
                    ++i;
                }
            }

            // put the pivot back in place
            t = seq[i];
            seq[i] = seq[e-1];
            seq[e-1] = t;

            // recurse on sub-arrays
            rec(s, i);
            rec(i + 1, e);
        }
        rec(0, seq.length);
    }

    function funcQuickSort2(seq, comp) {
        function rec(s, e) {
            var l, m, t, pivot, i, j, n, cr;
            for (;;) {
                l = e - s;
                if (l <= 1) {
                    return;
                }

                // choose a pivot
                m = s + (l >> 1);
                pivot = seq[m];

                i = j = s;
                n = e - 1;
                while (j <= n) {
                    cr = comp(seq[j], pivot);
                    if (cr < 0) {
                        t = seq[i];
                        seq[i] = seq[j];
                        seq[j] = t;
                        i += 1;
                        j += 1;
                    } else if (cr > 0) {
                        t = seq[n];
                        seq[n] = seq[j];
                        seq[j] = t;
                        n -= 1;
                    } else {
                        j += 1;
                    }
                }

                // recurse on sub-arrays
                rec(s, i);
                // recursion on second sub-array is handled by loop
                // (tail call optimization)
                s = n + 1;
            }
        }
        rec(0, seq.length);
    }

    function boundFuncQuickSort(seq) {
        return funcQuickSort(seq, compItems);
    }

    function boundFuncQuickSort2(seq) {
        return funcQuickSort2(seq, compItems);
    }

    function runTests(progresscb) {
        var tempLimit = {};
        //tempLimit = {'*': 10};
        var data = testAlgos([
            { func: boundFuncQuickSort, name: 'boundFuncQuickSort', limits: {'identical': 500} },
            { func: boundFuncQuickSort2, name: 'boundFuncQuickSort2', limits: tempLimit },
            { func: insertionSort, name: 'insertionSort', limits: {'unordered': 10000} },
            { func: mergeSort, name: 'mergeSort', limits: tempLimit },
            { func: heapSort, name: 'heapSort', limits: tempLimit },
            { func: quickSort, name: 'quickSort', limits: {'identical': 500} },
            { func: quickSort2, name: 'quickSort2', limits: tempLimit },
            { func: arraySort, name: 'arraySort', limits: tempLimit },
        ], progresscb);
        return data;
    }

    // do the export of visible symbols
    exports.runTests = runTests;
}(typeof exports === 'undefined' ? this['bench'] = {} : exports));
